One conventional mechanism to control information release utilizes anonymization. Referring now to FIG. 1, a conventional Chaumian Mix mechanism is shown. As seen, digital mixes 101 and 103 create hard-to-trace communications using a chain of proxies such that an external observer will not be able to “link” output messages 105A, 105B and 105C to input messages 107A, 107B and 107C (that is, the digital mixes create “unlinkability”). Such mechanisms are typically used in anonymizing IP networks, such as Tor and Onion routing.
In recent years, privacy protection has become a critical issue for location based services (sometimes referred to herein as “LBS”) users. For example, a massive volume of spatio-temporal data is available that potentially reveals user habits, interests and activities (and which can be exploited for illicit gain via theft, blackmail or even physical violence).
Several studies show how to help protect users by anonymizing location traces, i.e., data that captures a sequence of space-time points visited by the users. Referring, for example, to Mix Zones: User Privacy in Location-aware Services, Laboratory for Communication Engineering, University of Cambridge, Beresford et al., a set of users {a, b, c} enter a mix-zone at time t (t is not an “instant”, it is a “time window”). The same set of users leave the mix-zone at time t but with different pseudo-identifiers (e.g., {a, b, c}→{q, r, s}). The goal is to ensure that entering and exiting users cannot be “linked”.
However, “side-channels” (e.g., timing channel, social side-channel, local spatial constraints (Markovian)) have been used in the past as auxiliary information to deanonymize data (that is, where anonymized data+auxiliary information=deanonymized data).
One specific conventional mechanism has examined linkages that can be deduced using timing information heuristics such as left/right turn (in the United States you drive on the right hand side of the road, so a left turn takes more time).
As mentioned above, utilizing mix-zones to break trajectories into unlinkable segments can help increase privacy significantly. However, conventional models typically assume that attackers use timing analysis and/or local factors (e.g., on roads in the United States a right turn is typically faster than a left turn). As described herein, many of these conventional assumptions are inadequate; and they may result in an over-estimation of privacy.